package 纯完全背包;

import java.util.Arrays;

/**
 * @author: AirMan
 * @date: 2025/5/10 13:51
 * @description:
 */
public class Solution2 {
    public int completeBackpack(int[] weigh, int[] values, int bagSize) {
        // 纯完全背包问题
        // ① dp数组及其含义：dp[i]表示背包容量为i时，从前面的物品中无限选择物品，所能装下的最大价值数
        // ② 动态转移方程：dp[i] = Math.max(dp[i], dp[i-weig[i]] + values[i]);
        // ③ dp数组的初始化：根据物品0的重量和背包重量，能装就装
        // ④ 遍历顺序：先遍历物品再遍历背包，不同于01背包，完全背包需要从背包容量0遍历到最大容量
        // ⑤ 举例推导dp数组：输入weigh = [1,3,4] value = [10, 20, 65], bagSize = 4
        //     index:       0   1   2   3   4
        //                  0   15  30  45  60
        //                  0   15  30  45  60
        //                  0   15  30  45  65

        int[] dp = new int[bagSize + 1];

        // 这里有讲究了，不同于01背包问题。这里的遍历顺序时可以颠倒的，具体的变化时《排列》和《组合》的区别
        for (int j = 0; j < weigh.length; j++) {
            for (int i = 0; i <= bagSize; i++) {
                if (i >= weigh[j]) {
                    dp[i] = Math.max(dp[i], dp[i - weigh[j]] + values[j]);
                }
            }
            System.out.println(Arrays.toString(dp));
        }

        return dp[bagSize];
    }
}
